package com.linchong.dynamicprogramming.test;

/**
 * @author linchong
 * @version 1.0
 * @Date: 2020-11-20 17:09
 * @Description: PalindromePartitioningII$132-分隔回文串-https://leetcode-cn.com/problems/palindrome-partitioning-ii/
 */
public class PalindromePartitioningII {
	/**
	 *
	 * 给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。
	 *
	 * 返回符合要求的最少分割次数。
	 *
	 * 示例:
	 *
	 * 输入: "aab"
	 * 输出: 1
	 * 解释: 进行一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
	 *
	 * 来源：力扣（LeetCode）
	 * 链接：https://leetcode-cn.com/problems/palindrome-partitioning-ii
	 *
	 * step1：确定状态：
	 *      最后一步：
	 *          最优策略中最后一段回文串，设为S[j...N-1],需要知道S的前j-1个字符最少划分为多少回文串
	 *      子问题：
	 *          求S[0-N-1]最少划分为几个回文串->S[0-j-1]最少划分为多少字符串
	 *      状态：
	 *          设S[i]=前i个字符最少可以划分文f[i]个回文串
	 * step2:状态转移方程
	 *          f[i] = min(j=0,1,2,...,i-1){f[j]+1|S[j,...,i-1]是回文串}
	 * step3:初始条件和转移方程
	 *          f[0]=0
	 * step4:计算：
	 *          f[0],f[1],f[2],...,f[n]
	 *
	 * 计算回文串方法
	 *
	 */

	public int minCut(String s) {
		char[] chars = s.toCharArray();
		int n = chars.length;

		boolean[][] isPalin = new boolean[n][n];
		int i,j,t;

		for (i = 0; i < n; i++) {
			for (j = i; j < n; j++) {
				isPalin[i][j] = false;
			}
		}

		int[] f = new int[n];

		f[0] = 0;

		// 生成回文串
		for (t = 0; t < n; t++) {
			// 计算奇数
			i = j =t;
			while (i>=0&&j<n&&chars[i]==chars[j]){
				isPalin[i][j] = true;
				i--;
				j++;
			}

			//计算偶数
			i = t;
			j = t+1;

			while (i>=0&&j<n&&chars[i]==chars[j]){
				isPalin[i][j] = true;
				i--;
				j++;
			}
		}
		
		// 计算最小值
		//f[i] = min(j=0,1,2,...,i-1){f[j]+1|S[j,...,i-1]是回文串}
		for (i= 1; i <= n; i++) {
			for (j = 0;  j<i ; j++) {
				f[i] = n;
				if(isPalin[j][i-1]){
					f[i] = Math.min(f[j]+1,f[i]);
				}
			}
		}


		return f[n]-1;
	}

	public static void main(String[] args) {
		String str = "aab";
		PalindromePartitioningII instance = new PalindromePartitioningII();
		System.out.println(instance.minCut(str));

	}
}
